package alogrithm.heap;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 大根堆数据结构
 * 
 * @author Administrator
 * 
 */
public class BigHeap<T> {
	public T data[];

	public String toString(){
		return Arrays.toString(data);
	}
	public BigHeap(T data[]) {
		this.data = data;
		buildHeap(this.data);
	}

	public static void main(String[] args) {
		Integer a[]=new Integer[] { 8, 7, 3, 4, 5, 6, 2, 1 };
		BigHeap<Integer> hp=new BigHeap<Integer>(a);
		System.out.println(hp.pop());
		System.out.println(hp.pop());
		System.out.println(hp.pop());
		System.out.println(hp.pop());
		System.out.println(hp.pop());
	}
	private int index=1;
	public T pop(){
		T first=data[0];
		swap(data,0,data.length-index);
		adjustHeap(data, 0, data.length-index);
		index++;
		return first;
	}

	public void sort(){
		if(index>=data.length){
			return;
		}
		for(int i=0;i<data.length;i++){
			pop();
		}
	}
	public void buildHeap(T[] data) {
		if (data.length <= 0) {
			return;
		}

		int len = data.length;
		for (int i = (len>>>1)  ; i >= 0; i--) {
			adjustHeap(data, i, len);
		}

		System.out.println("大根堆为:" + Arrays.toString(data));
	}

	/**
	 * [1,2,3,4,5,6,7,8]
	 * 
	 * @param data
	 * @param i
	 * 
	 */
	public void adjustHeap(T[] data, int i, int len) {
		int l = left(i);
		int r = right(i);

		int largest = i;

		// 如果左边孩子节点的值比当前父节点的值大，则将largest标记为左边孩子的下标
		if (l < len && compare(data[l], data[i]) > 0) {
			largest = l;
		}

		// 如果右边孩子节点的值比最大值还大，则将largest更新为最大孩子的值
		if (r < len && compare(data[r], data[largest]) > 0) {
			largest = r;
		}

		// 如果最大值和当前父节点的值不相同，则交换2个值，否则不交换

		if (largest != i) {
			swap(data, i, largest);
			adjustHeap(data, largest, len);
		}
	}

	public void swap(T[] data, int i, int largest) {
		T temp = data[i];
		data[i] = data[largest];
		data[largest] = temp;
	}

	public int compare(T left, T right) {
		return ((Comparable) left).compareTo(right);
	}

	public int left(int i) {
		return i << 1;
	}

	public int right(int i) {
		return (i << 1) + 1;
	}

	public int parent(int i) {
		return i >> 1;
	}
}
